/*
 * @lc app=leetcode.cn id=589 lang=javascript
 *
 * [589] N 叉树的前序遍历
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
// var getNode = function(root, arr){
//   if(!root) return null;
//   arr.push(root.val);
//   root.children.forEach(item=>{
//     getNode(item, arr);
//   })
// }
// var preorder = function(root) {
//   let arr = [];
//   getNode(root, arr);
//   return arr;
// };

// var preorder = function(root) {
//   if(!root) return [];
//   let arr = [];
//   let stack = [root];
//   while(stack.length>0){
//     let node = stack.pop();
//     arr.push(node.val)
//     for (let i = node.children.length - 1; i > -1; i--) {
//       stack.push(node.children[i])
//     }
//   }
//   return arr;
// };

/**
 * 复习 2021-08-04
 */
// var getNode = function(root,ret) {
//   if(!root) return [];
//   ret.push(root.val);
//   if(root.children){
//     for (let i = 0; i < root.children.length; i++) {
//       getNode(root.children[i], ret);
//     }
//   }
// }
// var preorder = function(root) { 
//   if(!root) return [];
//   let ret  = [];
//   getNode(root, ret);
//   return ret;
// }

// 循环 + 栈代替递归
var preorder = function(root) { 
  if(!root) return [];
  let ret  = [];
  let stack = [root];

  while(stack.length){
    let node = stack.pop();
    ret.push(node.val);
    if(node.children){
      for (let i = node.children.length - 1; i >=0 ; i--) {
        stack.push(node.children[i])
      }
    }
  }
  return ret;
}
// @lc code=end

